Red-Black Trees

Properties of red-black trees

• A red-black tree is a binary search tree with one extra bit of storage per node: its color, which can be either RED or BLACK.
• Each node of the tree now contains the attributes color, key, left, right, and p
• A red-black tree is a binary tree that satisfies the following red-black properties:
  • Every node is either red or black
  • The root is black
  • Every leaf (NIL) is black
  • If a node is red, then both its children are black
  • For each node, all simple paths from the node to descendant leaves contain the same number of black nodes
• We call the number of black nodes on any simple path from, but not including, a node x down to a leaf the black-height of the node, denoted
• Lemma 13.1:A red-black tree with internal nodes has height at most

Rotations

• We change the pointer structure through rotation, which is a local operation in a search tree that preserves the binary-search-tree property
• the two kinds of rotations: left rotations and right rotations.

LEFT-ROTATE（T,x） 
1 y = x.right     // set y
2 x.right = y.left   // turn y's left subtree into x's right subtree
3 if y.left ≠ T.nil 
4    y.left.p = x 
5 y.p = x.p        // link x's parent to y
6 if x.p == T.nil 
7    T.root = Y 
8 elseif x == x.p.left 
9 x.p.left = y 
10 else x.p.right = y 
11 y.left = x    // put x on y's left
12 x.p = y 

• The code for RIGHT-ROTATE is symmetric. Both LEFT-ROTATE and RIGHT-ROTATE run in time.

Insertion

RB-INSERT（T,z） 
1 y = T.nil 
2 x = T.root 
3 while x ≠ T.nil 
4       y = x     
5       if z.key < x.key 
6          x = x.left 
7       else x = x.right 
8 z.p = y 
9 if y== T.nil 
10   T.root = z 
11 elseif z.key < y.key 
12   y.left = z 
13 else y.right = z 
14 z.left = T.nil 
15 z.right = T.nil 
16 z.color = RED 
17 RB-INSERT-FIXUP（T,z）

RB-INSERT-FIXUP（T,z） 
1 while z.p.color == RED 
2       if z.p == z.p.p.left 
3          y = z.p.p.right 
4          if y.color == RED 
5             z.p.color = BLACK //case1
6             y.color = BLACK   //case1
7             z.p.p.color = RED //case1
8             z = z.p.p         //case1
9          else if z == z.p.right 
10                 z = z.p           //case2
11                 LEFT-ROTATE（T,z） //case2
12              z.p.color = BLACK    //case3
13              z.p.p.color = RED    //case3
14              RIGHT-ROTATE（T,z.p.p)//case3
15         else （same as then clause with “right" and “'lefe exchanged） 
16 T.root.color = BLACK

• Moreover, it never performs more than two rotations, since the while loop terminates if case 2 or case 3 is executed.
• Thus, the only properties that might be violated are property 2, which requires the root to be black, and property 4, which says that a red node cannot have a red child
• Case 1: z’s uncle y is red;
• Case 2: z’s uncle y is black and z is a right child
• Case 3: z’s uncle y is black and z is a left child

Deletion

TRANSPLANT（T,u,v） 
1 if u.p == T.nil 
2    T.root = v 
3 elseif u == u.p.left 
4    u.p.left =v 
5 else u.p.right=v 
6 v.p = u.p

• The procedure RB-TRANSPLANT differs from TRANSPLANT in two ways.
  • First, line 1 references the sentinel T.nil instead of NIL.
  • Second, the assignment to v.p in line 6 occurs unconditionally

RB-DELETE（T,z） 
1 y = z 
2 y-original-color = y.color 
3 if z.left == T.nil 
4     x = z.right 
5     RB-TRANSPLANT（T, z, z.right） 
6 elseif z.right == T.nil 
7     x = z.left 
8     RB-TRANSPLANT（T, z, z.left） 
9 else y = TREE-MINIMUM（z.right） 
10    y-original-color = y.color 
11    x = y.right 
12    if y.p == z 
13       x.p = y 
14    else RB-TRANSPLANT（T, y, y.right） 
15         y.right= z.right 
16         y.right.p = y 
17    RB-TRANSPLANT（T, z.y） 
18    y.left = z.left 
19    y.left.p = y 
20    y.color = z.color 
21 if y-original-color == BLACK 
22    RB-DELETE-FIXUP（T,x）

RB-DELETE-FIXUP（T,x） 
1 while x ≠ T.root and x.color == BLACK 
2      if x == x.p.left 
3         w = x.p.right 
4         if w.color == RED 
5            w.color = BLACK //case1
6            x.p.color = RED //case1
7            LEFT-ROTATE（T,x.p） //case1
8            w= x.p.right //case1
9         if w.left.color == BLACK and w.right.color == BLACK 
10           w.color = RED //case2 
11           x=x.p //case2
12        else if w.right.color == BLACK 
13           w.left.color = BLACK //case3
14           w.color = RED //case3
15           RIGHT-ROTATE（T,w） //case3
16           w= x.p.right //case3
17        w.color = x.p.color //case4
18        x.p.color = BLACK //case4
19        w.right.color = BLACK //case4
20        LEFT-ROTATE（T,x.p） //case4
21        x = T.root //case4
22     else （same as then clause with “right”and "left’ exchanged） 
23 x.color = BLACK

• Case 1: x’s sibling w is red
• Case 2: x’s sibling w is black, and both of w’s children are black
• Case 3: x’s sibling w is black, w’s left child is red, and w’s right child is black
• Case 4: x’s sibling w is black, and w’s right child is red